package prefixSumStudy;

import java.util.HashMap;

/**
 * 前缀和+哈希表进行优化
 */
public class PrefixSumStudy01 {

    /**
     * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
     *
     * 前缀和+哈希表优化
     * @param args
     */
    public static void main(String[] args) {

    }

    /**
     * 前缀赋值第一个可以为零，方便计算
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k){
        //求出前缀和
        int[] prefix = new int[nums.length+1];
        //初始化第一个值
        prefix[0] = 0;
        //初始化前缀和
        for (int i = 1; i < prefix.length; i++){
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        //记录合格的数量
        int count = 0;
        //初始化map数组
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 1; i < prefix.length; i++){
            if (map.keySet().contains(prefix[i] - k)){
                count += map.get(prefix[i] - k);
            }
            map.put(prefix[i], map.getOrDefault(prefix[i], 0) + 1);
        }
        return count;
    }
}
